package com.spacewiz13.algorithm.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]
 * @author David
 *
 */
public class BinaryTreeLevelOrderTraversalII {
	
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
    	if(root==null)
    		return new ArrayList<List<Integer>>();
    	
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<TreeNode> nodeList = null;
        List<Integer> valList = null;
        Stack<List<Integer>> stack = new Stack<List<Integer>>();
        queue.add(root);
        
        while(!queue.isEmpty()){
        	nodeList = new ArrayList<TreeNode>();
        	valList = new ArrayList<Integer>();
            while(!queue.isEmpty()){
            	TreeNode node = queue.poll();
            	if(node!=null){
                	nodeList.add(node);
                	valList.add(node.val);
            	}

            }
            if(!valList.isEmpty())
            	stack.add(valList);
            for(TreeNode node:nodeList){
            	queue.add(node.left);
            	queue.add(node.right);
            }
        }
        
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        while(!stack.isEmpty()){
        	resultList.add(stack.pop());
        }

        
    	return resultList;
    }
	
	
}
